# 从前往后比，比后面的数小就插入在这个数的前面
def directInsertSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i):
            if arr[i] < arr[j]:
                arr.insert(j,arr.pop(i))
                break
    return arr
ilist = directInsertSort([4, 5, 6, 7, 3, 2, 6, 9, 8])
print(ilist)
# 从后往前，比他大就插入在他后面
# 把待排序的数组和已排序的数组比较选择插入的位置
# 这次是从前到后的插入
#从后到前
# why 逆序？><控制顺序和逆序
# 逆序遍历就需要多比较一个，因为比较的是谁大，都大不过就是最小的
# 顺序的话直接比较最小的，是最小就前插，最大不动就可以了！
# break是因为for到这后面都比这个大，就insert重复了
def directInsertSort(arr):
    n = len(arr)
    for i in range(n):
        isMin = True
        for j in range(i-1,-1,-1):
            if arr[i] >= arr[j]:
                arr.insert(j+1,arr.pop(i))
                isMin = False
                break
        if isMin:
            arr.insert(0,arr.pop(i))
    return arr

ilist = directInsertSort([4, 5, 6, 7, 3, 2, 6, 9, 8])
print(ilist)